//有序数组的平方
    //示例：
        //    输入：nums = [-4,-1,0,3,10]
        //    输出：[0,1,9,16,100]
int nums[];
int length = sizeof(nums)/sizeof(nums[0]);
    //方法一
        //先平方，后排序，排序使用冒泡排序 
functionOne(nums[]){
    for (int i = 0; i < length; i++){
        nums[i] *= nums[i];
    }
    for (int j = 0; j < length; j++){
        for (int k = 0; k < (length-1); k++){
            if (nums[k] > nums[k+1]){
                int change = nums[k];
                nums[k] = nums[k+1];
                nums[k+1] = change;
            }
        }
    }
}   
        //先按绝对值排序，后平方
functionTwo(nums[]){
    for(int i = 0; i < length; i++){
        for(int j = 0; j < (length-1); j++){
            if(abs(nums[j]) > abs(nums[j+1])){
                int change = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = change;
            }
        }
    }
    for(int k = 0; k < length; k++){
        nums[k] *= nums[k];
    }
}
        //空间复杂度由数据本身来定，数组，变量i,j,要交换的变量change，所以不会改变
        //1. n+n*n;  2. n*n+n;  所以时间复杂度是n的平方
        //考虑到排序的次数与数组元素本身的顺序有关，还可以再加上选择语句，以减少循环次数
        
        //对排序进行优化
void swap(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a  = *b;
    *b  = tmp;
    return;
}
static void _quickSort3(int nums[ ],int l,int r)
{
    int i, lt, gt;
    //变量lt为小于v和等于v的分割点,gt为大于v和未遍历元素分割点,gt指向未遍历元素
    if(l >= r)
    {
        return;
    }
    i = l + 1;
    lt = l;
    gt = r ;//递归对左右两部分进行快速排序直到每部分元素个数为1时则整个序列都是有序的
    while(i <= gt)
    {
        if(nums[i] < nums[l])
        {
            swap(&nums[lt + 1], &nums[i]);
            lt ++;
            i++;
        }
        else if(nums[i] > nums[l])
        {
            swap(&nums[i], &nums[gt]);
            gt--;
        }
        else
        {
            i++;
        }
    }
    swap(&nums[l], &nums[gt]);
    _quickSort3(nums, l, lt);
    _quickSort3(nums, gt + 1, r);
    return;
}
void quickSort(int nums[], int n)
{
    _quickSort3(nums, 0, n - 1);
    return;
}
    //方法二
        //双指针法
    int* sortedSquares(int* nums, int numsSize, int* returnSize){

    *returnSize = numsSize;
    int p=0, q=numsSize-1, index=numsSize;
    int *new=(int*)malloc(sizeof(int)*numsSize);

    while((index--)>0)
    {
        if(-nums[p]>nums[q]) {new[index]=nums[p]*nums[p]; p++;}
        else {new[index]=nums[q]*nums[q]; q--;}
    }

    return new;
}